greatcfandomcom-20200214-history
Research Proposal
Proof Based Design of General Purpose Mulitprocessor Computing Systems This page outlines a research plan to create a multiprocessor general purpose computing/operating system, called COS (Co-Operating System) that will lead to the delivery of guaranteed general purpose computing systems. Underlying this research plan is the following hypothesis: The proposal is to build general purpose computing systems where there is a large pool of processors and essentially one process runs on one processor. Having a single process per processor is a cornerstone of being able to prove programs correct. Proofs are simplified as a program will always execute as a single process on a well defined processor architecture and will not have to contend with interference from other processes. The allocation of processes to processors is achieved through a well defined and mathematically sound resource allocation mechanism. The resource allocation mechanism is based on an observable cellular broadcast structure. No single process is responsible for managing the allocation of resources. Having a distributed and observable resource allocation mechanism also allows for fault tolerance and extensibility. So that dynamic ad hoc networks of processes can be created the IPC channels are also handled by the resource allocation mechanism. Because this resource allocation mechanism makes the state of the system visible to resources it is possible to manage all resources as a feedback control problem. The architecture of a COS also addresses another major concern of modern computing systems - energy consumption. This is addressed in two ways. Firstly as a process owns the processor on which it is running it can power down whenever possible being powered back up when there are interrupts, message arrivals or timer events. Secondly when a processor is waiting for work it is powered down and is managed by a low power co-processor. The co-processor forms part of the distributed operating system. Processor Isolated Processes A key to the design of a COS is a change in the design objectives. There is a shift from the emphasis on the manufacturing (capital) costs of processors to the running costs. As with a pool of workers who only get paid (energy) when they are working, so in a COS, processors only consume energy when working. Early in the design of VLSI circuits a change in approach to the design of the silicon layout was needed as old design principles based around switching theory were no longer appropriate when LSI designs were transfered to silicon: Text below this line is rough notes only. Background * Current Situation ** Breakdown of computing, embedded, general purpose, super computers ** The software crisis ** Today's challenges ** Advances in computing systems * Problems being faced ** Writing programs that can make use of parallel computers. Today Moore's law already means that hardware has advanced far more rapidly than software. Improvements have largely been through Nearly all general purpose software today is developed in a non-rigorous manner and delivered with defects* that are "fixed" in the field. It is possible to build reliable systems using formal methods (Woodcock et al., 2009) A huge amount of effort is being invested in finding ways of building multiprocessor systems for general purpose computing. {Include references such as Intels research work into multicore systems http://techresearch.intel.com/articles/Tera-Scale/1449.htm }. Another quote to suport the argument: Background It is generally accepted that computing systems contain bugs (REF) and that fixing these bugs consumes a large proportion of the computing businesses resources (REF). Existing General Purpose Operating Systems Things to consider. * Microkernels * Real Time Systems * Formal Proofs * Multiprocessor Systems * Low Energy Computing * Problems with Threading * Erlang * CSP * Transputer * General Purpose Operating Systems Examples of general purpose operating systems: * Linux * Windows * FreeBSD * Coyotos * Hurd Multiprocessor Computers Multiprocessor Software Design The proposed design contains three main components, a processor pool, a decentralised resource allocation mechanism and a reconfigurable IPC network: * Processor Pool ** Large number of processors (> 1000) ** Simple Processor Design ** Fast Switch Off Switch On (SOSO) Processors ** Non-Volatile Processor/Memory * Decentralised Resource Allocation ** Cellular Broadcast Network ** Distibuted Queuing Protocol ** Eager Queue Protocol * Reconfigurable IPC Network ** Possibly an ethernet ** Possibly an omega network The design works as follows. A boot process starts a minimum number of processes with each process running on its own processor. The state of the processors is maintained by the decentralise resource allocation mechanism. This mechanism is based on a token that is "passed" between processors over a broadcast network. Each time a new process is required a processor is located by the decentralised resource allocation mechanism. Processor Pool To enable Proof Based Design each process executes on its own processor. So that there can be many processors a large pool of processors is required. In a tranditional operating system process has three states: * Running * Blocked * Ready MINIX - http://www.csd.uwo.ca/courses/CS3305a/Lectures/minix.ppt In this design a process only has two states: * Running * Blocked In Singularity (Hunt, Larus, 2007), . . . TODO... We have SHIPs, Software and Hardware Isolated Processes. Decentralised Resource Allocation Reconfigurable IPC Network Previous Work * http://developer.novell.com/wiki/index.php/OpenEd_-_Lab_4 Research Plan # Review the current state of general purpose operating systems # Review the current state of formal methods # Review of computer architectures # Development of ABC - A Boradcast Calculus # Proof of EQP # Definition of GPCS Category:Research